package array.bisection;

/**
 * @Author: 海琳琦
 * @Date: 2021/12/13 11:53
 *
 *给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 *
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 */
public class Title69 {
    public static void main(String[] args) {
        int result = mySqrt(2147395599);
        System.out.println(result);
    }

    private static int mySqrt(int x) {
        int start = 0, end  = x / 2 + 1;
        int middle;
        while(start<=end){
            middle = (start + end) / 2;
            if((long)middle*middle>x){
                end = middle - 1;
            }else if((long)middle*middle<x){
                start = middle + 1;
            }else{
                return middle;
            }
        }
        return end;
    }


}
